<?php

function noRecurrsive($n){
    if($n <= 0){
        return 0;
    }
    if($n == 1 || $n == 2){
        return 1;
    }

    $a = $c = 0;
    $b = 1;
    // n-1次相加
    for($i = 1; $i<$n; $i++){
        $c = $a + $b;
        $a = $b;
        $b = $c;
    }
    return $c;
}

global $i;
function recurrsive($n){
    $GLOBALS['i']++;
    if($n <= 0){
    	return 0;
    }
    if($n == 1 || $n == 2){
        return 1;
    }

    return recurrsive($n - 1) + recurrsive($n - 2);
}

function optimize($n, &$arr = []){
    $GLOBALS['i']++;
    if(array_key_exists($n, $arr)){
        return $arr[$n];
    }else{
        if($n <= 0){
            $arr[$n] = 0;
            return 0;
        }
        if($n == 1 || $n == 2){
            $arr[$n] = 1;
            return 1;
        }

        $res = optimize($n - 1, $arr) + optimize($n - 2, $arr);
        $arr[$n] = $res;
        return $res;
    }
}

$start = time();
var_dump("非递归的算法：结果为" . noRecurrsive(40). " 耗时为：" . (time() - $start));

$start = time();
var_dump("未优化的递归：结果为" . recurrsive(40) . " 调用次数为：" . $GLOBALS['i'] . " 耗时为：" . (time() - $start));

$start = time();
$GLOBALS['i'] = 0;
var_dump("优化过的递归：结果为" . optimize(50) . " 调用次数为：" . $GLOBALS['i'] . " 耗时为：" . (time() - $start));